LeetCode 680、验证回文串II

一、题目描述

给你一个字符串 s，最多 可以从中删除一个字符。

请你判断 s 是否能成为回文字符串：如果能，返回 true ；否则，返回 false 。

示例 1：

输入：s = "aba" 输出：true

示例 2：

输入：s = "abca" 输出：true 解释：你可以删除字符 'c' 。

示例 3：

输入：s = "abc" 输出：false

提示：

• 1 <= s.length <= 10^5
• s 由小写英文字母组成

二、题目解析

三、参考代码

class Solution:
    def validPalindrome(self, s: str) -> bool:

        # 判断 [ low , hight ] 这个区间的字符串是否是回文串
        def isPalindrome(low, high):

            # 左边索引的位置在 low 开始 
            left = low

            # 右边索引的位置在 high
            right = high

            # 两个索引向内移动
            # left 向右移动
            # right 向左移动
            while left < right:
                
                # 判断这两个元素值是否相同
                if s[left] != s[right]:
                    # 如果不同，直接返回 False
                    return False
                    
                # 否则，left 向右移动
                left += 1
                # right 向左移动
                right -= 1

            # 返回结果
            return True

        # 左边索引的位置在 0 开始 
        low = 0
        
        # 右边索引的位置在 len(s) - 1
        high = len(s) - 1

        # 两个索引向内移动
        # left 向右移动
        # right 向左移动
        while low < high:

            # 1、判断这两个元素值是否相同
            # 如果相同
            if s[low] == s[high]: 

                # 两个索引向内移动
                low += 1

                high -= 1

            # 2、如果不相同
            else:
                # 3、删除 low 所在这个元素，判断 [ low + 1 , high ] 是否是回文串
                # 或者
                # 4、删除 high 所在这个元素，判断 [ low  , high - 1 ] 是否是回文串
                return isPalindrome(low + 1, high) or isPalindrome(low, high - 1)
        
        # 返回结果
        return True